package algocasts;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class P98_wordBreak {
    // Time: O(n^2)  Space: O(n+m)
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] d = new boolean[n + 1];
        d[0] = true;
        Set<String> set = new HashSet<>(wordDict);
        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= 0; --j) {
                if (d[j] && set.contains(s.substring(j, i))) {
                    d[i] = true;
                    break;
                }
            }
        }
        return d[n];
    }
}
